W15. Maximum Flow Algorithms

1. Theory

1.1 Flow Networks

1.1.1 Directed Networks with Capacities

A flow network is a directed graph used to model movement of some resource from a distinguished source to a distinguished sink . The resource may be data in a communication network, goods in a transportation system, assignments in a matching problem, or pixels assigned to regions in an image-segmentation problem.

Each directed edge has a nonnegative capacity . Capacity is the maximum amount of flow that the edge can carry. By convention, if , then .

The standard model assumes:

• ;
• no edges enter the source ;
• no edges leave the sink ;
• no anti-parallel edge pair appears directly, so if , then .

These restrictions simplify the theory without reducing modeling power. If a real system has several sources, add a new super-source and connect it to every original source by a very large-capacity edge. If it has several sinks, add a new super-sink and connect every original sink to by a very large-capacity edge. If a model needs anti-parallel edges, replace one of the two directions by a two-edge path through a dummy vertex.

1.1.2 Feasible Flows

A flow is a function that assigns a numerical amount of flow to each ordered pair of vertices. A feasible flow must satisfy two laws.

The capacity constraint says that no edge may carry negative flow or more flow than its capacity:

for all .

The flow-conservation constraint says that every internal vertex neither creates nor destroys flow. For every ,

That is, total incoming flow equals total outgoing flow. The source may create flow, and the sink may absorb it; all other vertices only pass it through.

The value of a flow is the total flow leaving the source:

By conservation, this is also equal to the total flow entering the sink. For example, if units leave on one edge and unit leaves on another, then , and the same units must eventually enter .

1.1.3 Maximum Flow Problem

The maximum-flow problem asks for a feasible flow of maximum possible value. It is an optimization problem: many feasible flows may exist, but we want the one that sends as much total flow as possible from to .

In the introductory lecture network, the sink has incoming capacities of and of , so no flow can exceed if these are the only edges into . A feasible flow with value therefore proves optimal: send units out through and through , route enough through to saturate , and send unit through .

The important lesson is that maximum flow is not only about local unused capacity. A bad earlier routing choice may need to be partly cancelled before a larger total flow becomes possible. That is why residual networks are necessary.

1.2 Residual Networks and Augmenting Paths

1.2.1 Residual Capacity

Given a current flow , the residual capacity describes how much additional flow can be pushed from to after accounting for the current choices:

The first case is ordinary unused capacity on a forward edge. The second case is more subtle: if , then we may send flow from back to in the residual graph, which means cancelling some of the earlier flow from to .

The residual network contains exactly the directed edges with positive residual capacity:

Reverse residual edges are essential. Without them, Ford-Fulkerson-style algorithms would be unable to undo unlucky augmenting paths. A previous path may have used a capacity-limited edge in a way that blocks a better global arrangement; the reverse residual edge gives the algorithm a legal way to reroute that flow.

1.2.2 Augmenting Paths

An augmenting path is a directed path from to in the residual network . If such a path exists, then the current flow is not maximal, because we can increase the flow along that path.

For an augmenting path , its bottleneck residual capacity is

This is the maximum amount that can be pushed through the entire path without violating some residual capacity. To augment:

• increase by on original forward edges of ;
• decrease by when uses a reverse residual edge corresponding to original edge .

The result is again a feasible flow, and its value increases by exactly .

1.2.3 Why Path Choice Matters

Ford-Fulkerson does not specify which augmenting path to choose. This matters because poor choices can produce many small augmentations.

Consider a network with capacities

If the algorithm repeatedly chooses paths that use the middle edge and then cancels it through a reverse residual edge, it may augment by only unit at a time. A better choice would use the two direct high-capacity routes and finish in two augmentations. This is the motivation for Edmonds-Karp, which fixes path choice by always using BFS.

1.3 Ford-Fulkerson Method

1.3.1 General Method

The Ford-Fulkerson method repeatedly improves a feasible flow by finding an augmenting path in the residual network.

FORD-FULKERSON-METHOD(G, s, t)
1  initialize flow f to 0
2  while there exists an augmenting path p in the residual network G_f
3      augment flow f along p
4  return f

The complete edge-update version is:

FORD-FULKERSON(G, s, t)
1  for each edge (u, v) in G.E
2      (u, v).f = 0
3  while there exists a path p from s to t in the residual network G_f
4      c_f(p) = min { c_f(u, v) : (u, v) is in p }
5      for each edge (u, v) in p
6          if (u, v) in G.E
7              (u, v).f = (u, v).f + c_f(p)
8          else (v, u).f = (v, u).f - c_f(p)
9  return f

The method starts with the zero flow, which is always feasible. Each iteration preserves feasibility and strictly increases the value. When no augmenting path remains, the max-flow min-cut theorem proves that the current flow is maximum.

1.3.2 Running Time

If capacities are integers and augmenting paths are found by DFS or BFS, each augmentation increases the flow value by at least . Therefore the number of augmentations is at most , where is a maximum flow.

Finding one augmenting path costs , which is for the usual connected network setting. Updating the path costs at most . Thus the common bound is

This is pseudo-polynomial, not strongly polynomial, because it depends on the numerical value of the maximum flow rather than only on the number of vertices and edges. If capacities are very large, may be huge even when the graph is small.

1.4 Cuts and the Max-Flow Min-Cut Theorem

1.4.1 Cuts in Flow Networks

A cut in a flow network is a partition of the vertex set such that

The capacity of the cut is

Only edges directed from to are counted. This is because a cut capacity measures how much flow can cross from the source side to the sink side. Edges from back to do not help send flow from to ; in the net-flow equation they subtract instead.

The net flow across a cut is

It counts flow crossing forward from the source side to the sink side, minus flow crossing back.

1.4.2 Net Flow Equals Flow Value

For every feasible flow and every cut ,

The reason is conservation. Start with the cut , where the net flow across the cut is exactly the flow leaving the source. If we move an internal vertex from to , the total net flow across the cut does not change, because that vertex has equal incoming and outgoing flow. Repeating this argument reaches any cut.

This immediately gives a key upper bound:

So every cut capacity is an upper bound on every feasible flow value. If we ever find a flow and a cut with equal value, both must be optimal.

1.4.3 Max-Flow Min-Cut Theorem

A minimum cut is a cut with minimum capacity among all cuts in the network.

The max-flow min-cut theorem states that for a flow in a network , the following are equivalent:

1. is a maximum flow;
2. the residual network contains no augmenting path;
3. for some cut .

The theorem gives both an algorithmic stopping condition and a certificate of optimality. When Ford-Fulkerson cannot find another augmenting path, let be the set of vertices reachable from in the residual network, and let . This cut has capacity exactly , so it is a minimum cut.

1.5 Edmonds-Karp Algorithm

1.5.1 BFS Augmenting Paths

Edmonds-Karp is the Ford-Fulkerson method with one specific rule: always choose a shortest augmenting path in the residual network, where “shortest” means fewest edges. This path is found by BFS.

This rule makes the algorithm deterministic enough for a polynomial-time analysis. Each augmentation still increases the flow value, but the important structural fact is stronger: BFS distances from in the sequence of residual graphs never decrease.

Intuitively, once an edge on a shortest augmenting path becomes saturated, it cannot become useful again as a critical bottleneck until residual distances have increased enough. This prevents the algorithm from oscillating through the same short bad choices indefinitely.

1.5.2 Running Time

Each BFS in a residual graph costs . Each augmentation saturates at least one edge on the chosen shortest path; such an edge is called critical for that augmentation.

In Edmonds-Karp, any directed edge can become critical only times. Since there are residual edges, the number of augmentations is . Multiplying by the BFS cost gives

Unlike the basic Ford-Fulkerson bound , this is polynomial in the graph size and does not depend on the numerical values of capacities.

1.6 Modeling Extensions

1.6.1 Bipartite Matching as Maximum Flow

Maximum bipartite matching reduces naturally to maximum flow. Given a bipartite graph :

1. create a source and connect to every vertex in with capacity ;
2. direct every original edge from to with capacity ;
3. connect every vertex in to a sink with capacity .

Any integral flow of value corresponds to a matching of size : a unit of flow through means match with . The capacity-1 edges from and into ensure that no vertex is used more than once.

1.6.2 Lower and Upper Bounds

Some network models require every edge to carry at least a lower bound and at most an upper bound . Feasibility can be reduced to an ordinary max-flow computation.

First, reserve the lower bound on each edge by defining residual demand:

Then compute each vertex’s imbalance caused by the reserved lower-bound flows. Add a super-source connected to vertices that already have excess forced inflow, and add a super-sink connected from vertices that already have excess forced outflow. Finally, run max flow and check whether all demand edges out of the super-source are saturated. If they are, a feasible circulation exists; otherwise no feasible flow satisfies all lower bounds.

---

2. Definitions

• Flow network: A directed graph with nonnegative edge capacities, a source , and a sink .
• Capacity : The maximum amount of flow allowed on directed edge .
• Source: The distinguished vertex where flow originates.
• Sink: The distinguished vertex where flow is absorbed.
• Super-source: An artificial source connected to multiple original sources to reduce a multi-source problem to a single-source problem.
• Super-sink: An artificial sink connected from multiple original sinks to reduce a multi-sink problem to a single-sink problem.
• Anti-parallel edges: A pair of directed edges and between the same two vertices.
• Feasible flow: A flow satisfying capacity constraints and flow conservation.
• Capacity constraint: The condition .
• Flow conservation: The condition that every internal vertex has total incoming flow equal to total outgoing flow.
• Flow value : The total amount of flow leaving the source, equivalently entering the sink.
• Maximum-flow problem: The problem of finding a feasible flow with maximum value.
• Residual capacity : The remaining amount that can be sent from to , including possible cancellation of opposite flow.
• Residual network : The directed graph containing all edges with positive residual capacity.
• Reverse residual edge: An edge in the residual network that represents the ability to cancel existing flow on an original edge.
• Augmenting path: A path from to in the residual network.
• Bottleneck residual capacity : The minimum residual capacity along an augmenting path .
• Ford-Fulkerson method: The generic augmenting-path method for computing maximum flow.
• Cut : A partition of vertices with and .
• Cut capacity : The total capacity of edges directed from to .
• Net flow across a cut : Flow from to minus flow from to .
• Minimum cut: A cut of minimum capacity among all source-sink cuts.
• Max-flow min-cut theorem: The theorem equating maximum flow value with minimum cut capacity.
• Edmonds-Karp algorithm: Ford-Fulkerson with BFS shortest augmenting paths.
• Critical edge: An edge saturated as the bottleneck of an augmenting path.
• Bipartite matching reduction: The construction that turns matching in into a unit-capacity max-flow problem.
• Lower-bound flow constraint: A requirement that an edge must carry at least a specified amount of flow.

---

3. Formulas

• Capacity constraint:
• Flow conservation: for
• Flow value:
• Residual capacity:
• Bottleneck of an augmenting path:
• Cut capacity:
• Net flow across a cut:
• Cut upper bound:
• Ford-Fulkerson with integer capacities:
• Edmonds-Karp augmentations:
• Edmonds-Karp running time:
• Lower-bound residual capacity:

---

4. Practice

4.1. Compute the Value of a Flow (Lecture 13, Example 1)

In the lecture flow example, edge labels are flow/capacity:

Compute the value and verify it using the sink side.

Click to see the solution

Key Concept: The value of a flow is the total flow leaving the source. By flow conservation, it must equal the total flow entering the sink.

The source has two outgoing edges:

Therefore

Now verify at the sink. The incoming edges to carry:

Thus the total flow entering the sink is

The two computations agree, as they must for any feasible flow.

Answer: .

4.2. Build a Residual Network (Lecture 13, Example 2)

For the current flow

list the positive residual capacities.

Click to see the solution

Key Concept: Each original edge may contribute a forward residual edge for unused capacity and a reverse residual edge for cancellable current flow.

Process each edge separately.

Original edge	Flow/capacity	Positive residual edges
		with capacity
		with capacity
		with capacity
		with capacity
		with capacity , with capacity
		with capacity , with capacity
		with capacity , with capacity
		with capacity , with capacity
		with capacity , with capacity
		with capacity

Every listed residual edge has positive capacity, so it belongs to .

Answer: The residual network consists of the positive residual edges listed in the table above.

4.3. Compute the Capacity of Two Cuts (Lecture 13, Task 1)

In the flow network from Section 1.1.1, compute the capacity of the following cuts:

and

Click to see the solution

Key Concept: Cut capacity counts only directed edges from the source side of the cut to the sink side. Edges going backward are not included.

For the first cut,

The edges from to are:

Therefore

For the second cut,

The lecture trace gives the crossing capacities from to as

Thus

Answer: The cut capacities are and .

4.4. Compute Net Flow Across a Cut (Lecture 13, Task 2)

For the cut

the lecture trace gives the crossing-flow calculation

Compute the net flow and explain the subtraction.

Click to see the solution

Key Concept: Net flow across a cut is forward crossing flow minus backward crossing flow.

The forward terms in the lecture calculation are

Their sum is

The final term is a backward crossing flow of , which must be subtracted because it goes from the sink side of the cut back to the source side.

Therefore

This value must match for the corresponding feasible flow, by the net-flow-across-a-cut lemma.

Answer: The net flow across the cut is .

4.5. Compute Max Flow and a Minimum Cut (Lecture 13, Task 3)

Apply Ford-Fulkerson to the network with capacities

Then provide one minimum cut and verify .

Click to see the solution

Key Concept: To prove a flow is maximum, it is enough to exhibit a cut with the same capacity.

First observe the sink-side upper bound. The only edges entering are:

Thus the cut with sink side has capacity

No flow can have value more than .

Now construct a feasible flow of value using augmenting paths.

1. Send units along This saturates and uses of the units on .

2. Send unit along This saturates .

3. Send unit along This saturates , , and fills the remaining capacity of .

4. Send unit along This fills the remaining capacity of .

The resulting nonzero flows are:

Check conservation:

• receives and sends .
• receives and sends .
• receives and sends .
• receives and sends .
• receives and sends .
• receives and sends .
• receives and sends .
• receives and sends .

The value is

The cut

has capacity

Since the feasible flow value equals the cut capacity, the max-flow min-cut theorem proves that this flow is maximum and this cut is minimum.

Answer: The maximum flow value is , and one minimum cut is all vertices except on the source side and on the sink side.

4.6. Run Edmonds-Karp on the Lecture Network (Lecture 13, Task 4)

Run Edmonds-Karp on the lecture network whose preserved BFS augmenting paths are:

1. with bottleneck ;
2. with bottleneck ;
3. with bottleneck .

Compute the final flow value and explain why these are Edmonds-Karp-style augmentations.

Click to see the solution

Key Concept: Edmonds-Karp always chooses a shortest augmenting path in the current residual graph, using BFS.

The preserved lecture trace lists the BFS-selected augmenting paths and their bottlenecks. We add the bottleneck values because each augmentation increases the flow value by exactly its bottleneck residual capacity.

The first path contributes

The second path contributes

The third path contributes

Therefore the final value reached by this trace is

The slide also records the cut-capacity check

and

These equalities are min-cut certificates: once a cut of capacity is found, no flow can exceed . Since the augmenting-path trace already constructs a flow of value , the flow is maximum.

The reason the paths are Edmonds-Karp-style paths is not their capacities but their selection rule: at each stage BFS searches the current residual network and chooses a path with the smallest number of residual edges.

Answer: The final maximum flow value in the lecture trace is .

4.7. Integer Capacities and Termination (Lecture 13, Task 5)

Show that if all capacities are integers, Ford-Fulkerson terminates and returns an integer maximum flow.

Click to see the solution

Key Concept: With integer capacities, every residual capacity and every bottleneck remains integer.

Initially all flows are zero, so all flows are integers. Assume all current flows are integers. Then every residual capacity is computed as either

or

Both are integers. Therefore the bottleneck of any augmenting path,

is also a positive integer.

When we augment, each changed edge has its flow increased or decreased by this integer bottleneck, so all flows remain integers. Also, the flow value increases by at least in every iteration.

The value of any flow is bounded above by the capacity of every cut, for example the cut . Since this upper bound is finite, Ford-Fulkerson can perform only finitely many integer increases.

When the algorithm stops, there is no augmenting path. By the max-flow min-cut theorem, the current flow is maximum.

Answer: Integer capacities imply integer bottlenecks, so the flow value increases by at least per iteration and cannot exceed a finite cut capacity; termination and optimality follow.

4.8. Construct a Bad DFS Example (Lecture 13, Task 6)

Construct a network where DFS-based Ford-Fulkerson performs many more augmentations than Edmonds-Karp.

Click to see the solution

Key Concept: DFS can repeatedly choose long or unlucky paths through a small bottleneck, while Edmonds-Karp chooses shortest paths that avoid that behavior.

Use the four-vertex network

If DFS explores before and chooses

then the bottleneck is , because of edge . After this augmentation, a reverse residual edge of capacity appears.

DFS may next choose

using that reverse edge, again augmenting only unit. With an unlucky adjacency order, the algorithm can alternate these small improvements many times, requiring augmentations in this concrete instance and augmentations if the large capacities are .

Edmonds-Karp, however, uses BFS. It first finds shortest paths of length , such as

and

Each has bottleneck , so Edmonds-Karp finishes in two augmentations.

Answer: The network with two -capacity direct branches and a -capacity middle edge makes DFS-based Ford-Fulkerson much worse than Edmonds-Karp.

4.9. Recover a Minimum Cut from a Maximum Flow (Lecture 13, Task 7)

Given a maximum flow , show how to recover a minimum cut in time using the residual graph.

Click to see the solution

Key Concept: After a maximum flow, the residual network has no augmenting path from to .

Build the residual network . Then run DFS or BFS from in and let

Let

Because is maximum, there is no augmenting path, so is not reachable from in . Therefore , and is a valid cut.

Now consider any original edge with and . If it had unused capacity, then , so would be reachable from in the residual network. That contradicts . Hence every edge from to is saturated.

Similarly, any original edge from to carries zero flow; otherwise its reverse residual edge would allow reachability back into .

Thus the net flow across the cut equals its capacity:

By the max-flow min-cut theorem, this cut is minimum.

The DFS or BFS scans each residual edge at most once, so the running time is

Answer: Take the vertices reachable from in the final residual graph as ; the cut is minimum and is found in time.

4.10. Monotonic BFS Distances in Edmonds-Karp (Lecture 13, Task 8)

Prove that in Edmonds-Karp, the BFS distance from to any vertex in the residual graphs never decreases.

Click to see the solution

Key Concept: New residual edges created by augmentation are reverse edges of the chosen shortest path, and they point from a larger BFS layer to a smaller one.

Let be the BFS distance from to vertex in the residual network before an augmentation. Edmonds-Karp chooses a shortest augmenting path, so every edge on that path satisfies

After augmenting, some forward edges on the path may disappear if they become saturated. The only new edges that can appear are reverse edges. If the path used , the new reverse edge is .

Before augmentation,

so the reverse edge points from layer back to layer . Such an edge cannot create a shorter route from to , because was already one layer closer than .

For contradiction, suppose some vertex distance decreases for the first time after an augmentation. Let be the first vertex on a newly shorter path whose new distance is smaller than before, and let be the edge that enters it on that new shortest path. This edge must be newly created, because otherwise the same shorter path would have existed before. Therefore is a reverse edge of some augmented edge .

But then before augmentation the chosen BFS path had

The new path reaches before , so it would imply a route to shorter than its old BFS distance, contradicting the choice of as the first decreased vertex and the old BFS layering.

Hence no BFS distance can decrease.

Answer: New residual edges go backward along old BFS layers, so they cannot create shorter paths from ; all residual BFS distances are monotonically nondecreasing.

4.11. Reduce Bipartite Matching to Max Flow (Lecture 13, Task 9)

In a bipartite graph , reduce maximum bipartite matching to maximum flow and justify correctness.

Click to see the solution

Key Concept: Unit capacities enforce the rule that each vertex can participate in at most one matched edge.

Construct a flow network as follows:

1. Add a source .
2. Add an edge of capacity for every .
3. Direct every bipartite edge from left to right: for each with and , add with capacity .
4. Add an edge of capacity for every .

Now prove the two directions.

First, any matching of size gives a flow of value . For each matched edge , send one unit along

No vertex is used twice in a matching, so no capacity-1 edge out of or into is exceeded.

Second, any integral flow of value gives a matching of size . Choose exactly those bipartite edges that carry one unit of flow. Since every edge has capacity , each left vertex is used at most once. Since every edge has capacity , each right vertex is used at most once. Therefore the selected edges form a matching.

The integrality theorem for max flow applies because all capacities are integers, so there exists an integral maximum flow.

Answer: Add a unit-capacity source edge to each left vertex, unit-capacity directed bipartite edges, and unit-capacity sink edges from right vertices; maximum integral flow value equals maximum matching size.

4.12. Lower and Upper Capacity Bounds (Lecture 13, Task 10)

Suppose each edge has both lower and upper capacity bounds. Outline how to reduce feasibility of such a circulation to one max-flow computation.

Click to see the solution

Key Concept: Lower bounds can be pre-sent, leaving a balance problem that ordinary max flow can check.

Let every edge require

First subtract the lower bound from each edge by defining a new capacity

Think of units as already forced through edge . This creates imbalances at vertices. For each vertex , compute

If , then has received too much forced inflow and must send out units in the adjusted network. If , then has sent too much forced outflow and must receive units.

Create a super-source and a super-sink :

• if , add with capacity ;
• if , add with capacity .

Keep every original edge with adjusted capacity . Run max flow from to .

There is a feasible circulation with lower bounds if and only if every edge leaving is saturated. If saturation succeeds, combine the computed adjusted flow with the reserved lower bounds:

If some demand edge is not saturated, the required lower-bound imbalances cannot be repaired, so no feasible circulation exists.

Answer: Subtract lower bounds, add super-source and super-sink edges for vertex imbalances, run one max-flow computation, and check whether all super-source edges are saturated.